#다이나믹 프로그래밍
이 태그가 달린 글 3편입니다.
코딩 인터뷰
[코딩 인터뷰 준비] Edit distance - 편집 거리 알고리즘
너무나 유명한 고전 알고리즘입니다. 편집 거리는 문자열 유사도를 수량화하는 방법으로, 자연어 처리와 생물정보학에서 폭넓게 사용되고 있습니다. 코딩 인터뷰 단골 주제이기도 합니다.
읽기 코딩 인터뷰
[LeetCode 1143] LCS 최장 공통 부분 수열, 재귀로 풀다 TLE 맞고 배운 다이나믹 프로그래밍
LCS 재귀에서 TLE 맞고, 글자 다를 때 +1 실수 직접 해보고, dp[n-1][m-1] 함정 두 번 밟은 경험을 바탕으로 정리한 DP 실전 가이드입니다.
읽기 코딩 인터뷰
다이나믹 프로그래밍 - 여러 번 주사위 굴려서 정해진 숫자 맞추기
처음엔 Coin Change 2 복붙하면 된다고 생각했는데, Wrong Answer를 3번 받고 나서야 '정확히 n개를 전부 써야 한다'는 결정적 차이를 깨달았습니다. 모듈로를 마지막에만 적용해 오버플로가 났던 경험, base case를 0으로 초기화해 결과가 전부 0이 되었던 삽질까지 함께 정리합니다.
읽기